import java.util.HashMap;
import java.util.Map;

public class Solution_70 {

    Map<Long, Long> memo = new HashMap<>();
    public Long climbStairs(Long n) {
        if (n == 1l) return 1l;
        if (n == 2l) return 2l;
        if (memo.size() >= n) return memo.get(n);
        memo.put(n, climbStairs(n - 1) + climbStairs(n - 2));
        return memo.get(n);
    }


    public static void main(String[] args) {
        Long res = new Solution_70().climbStairs(49l);
        System.out.println(res);
    }
}
